import { param1, param2 } from "./temp";
import { fastSort } from "./fastsort";
/*
1. 两数之和
    给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
    你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
    示例:
    给定 nums = [2, 7, 11, 15], target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
*/
(function () {
    const twoSum = function (nums: number[], target: number) {
        if (isNaN(target) || !Array.isArray(nums)) {
            return [];
        }

        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (target - nums[i] === nums[j]) {
                    return [i, j];
                }
            }
        }
        return [];
    };
    console.log("twoSum:" + twoSum([3, 2, 4], 6));
})();

/* 
    给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
    示例 1:
    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    示例 2:
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
    示例 3:
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
        请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
*/

/**
 * @param {string} s
 * @return {number}
 */
(function () {
    const lengthOfLongestSubstring = function (s: string) {
        const strArr = Array.from(s);
        if (strArr.length < 1) return 0;
        let lastLength = 0;
        for (let i = 0; i < strArr.length; i++) {
            lastLength =
                lastLength < calcSubArr(strArr, i).length
                    ? calcSubArr(strArr, i).length
                    : lastLength;
        }
        return lastLength;
    };

    const calcSubArr = (strArr: string[], index: number) => {
        let _arr: string[] = [];
        for (let i = index; i < strArr.length; i++) {
            if (!_arr.includes(strArr[i])) {
                _arr.push(strArr[i]);
            } else {
                break;
            }
        }
        return _arr;
    };

    console.log(
        "lengthOfLongestSubstring:" + lengthOfLongestSubstring("pwwkew")
    );
    console.log("lengthOfLongestSubstring:" + lengthOfLongestSubstring(""));
})();

/*
    给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
    示例 1:
    输入: 123
    输出: 321
    示例 2:
    输入: -123
    输出: -321
    示例 3:
    输入: 120
    输出: 21
    注意:
    假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
*/
(function () {
    var reverse = function (x: number) {
        //let ret = parseInt(Array.from("" + Math.abs(x)).reverse().join(""));
        let arr = Array.from("" + Math.abs(x));
        let length = arr.length;
        let str = "";
        for (let i = length - 1; i >= 0; i--) {
            str += arr[i];
        }
        let ret = parseInt(str);
        if (ret > 2147483647) return 0;
        return x < 0 ? -ret : ret;
    };

    console.log("reverse:" + reverse(123));
})();

/*
    请你来实现一个 atoi 函数，使其能将字符串转换成整数。
    首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
    当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
    该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
    注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
    在任何情况下，若函数不能进行有效的转换时，请返回 0。
    说明：
    假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，qing返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
    示例 1:
    输入: "42"
    输出: 42
    示例 2:
    输入: "   -42"
    输出: -42
    解释: 第一个非空白字符为 '-', 它是一个负号。
        我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
    示例 3:
    输入: "4193 with words"
    输出: 4193
    解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
    示例 4:
    输入: "words and 987"
    输出: 0
    解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
        因此无法执行有效的转换。
    示例 5:
    输入: "-91283472332"
    输出: -2147483648
    解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
        因此返回 INT_MIN (−231) 。
*/

/**
 * @param {string} str
 * @return {number}
 */
(function () {
    var myAtoi = function (str: string) {
        const VAILD_MAP = ["+", "-"];
        const MIN = -2147483648;
        const MAX = 2147483647;
        const strArr: any[] = Array.from(str);
        let valArr = [];
        for (let i = 0; i < strArr.length; i++) {
            if (!strArr[i] || strArr[i] === " ") {
                if (valArr.length > 0) break;
                else continue;
            }
            if (!isNaN(strArr[i])) {
                valArr.push(strArr[i]);
            } else if (VAILD_MAP.includes(strArr[i]) && valArr.length < 1) {
                valArr.push(strArr[i]);
            } else {
                break;
            }
        }
        const val = parseInt(valArr.join(""));
        if (valArr.length < 1 || isNaN(val)) return 0;
        return val > MAX ? MAX : val < MIN ? MIN : val;
    };

    console.log("myAtoi:" + myAtoi("42"));
    console.log("myAtoi:" + myAtoi(" -42"));
})();

/* 
    判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
    示例 1:
    输入: 121
    输出: true
    示例 2:
    输入: -121
    输出: false
    解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
    示例 3:
    输入: 10
    输出: false
    解释: 从右向左读, 为 01 。因此它不是一个回文数。
    进阶:
    你能不将整数转为字符串来解决这个问题吗？
*/
/**
 * @param {number} x
 * @return {boolean}
 */
(function () {
    function isPalindrome(x: number) {
        if (x < 0) return false;

        const strArr = Array.from("" + x);
        const arrLen = strArr.length;
        if (arrLen === 1) return true;

        const left = strArr.slice(0, arrLen / 2);
        const right = strArr.slice(Math.round(arrLen / 2), arrLen);
        let mid = arrLen % 2 === 0 ? "" : strArr[parseInt(arrLen / 2 + "")];
        return left.join(mid) === right.reverse().join(mid);
    }

    console.log("isPalindrome: " + isPalindrome(10));
})();

/* 
    罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
    字符          数值
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000
    例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
    通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
    I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
    X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
    C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
    给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

    示例 1:
    输入: "III"
    输出: 3
    示例 2:
    输入: "IV"
    输出: 4
    示例 3:
    输入: "IX"
    输出: 9
    示例 4:
    输入: "LVIII"
    输出: 58
    解释: L = 50, V= 5, III = 3.
    示例 5:
    输入: "MCMXCIV"
    输出: 1994
    解释: M = 1000, CM = 900, XC = 90, IV = 4.
*/
(function () {
    var romanToInt = function (s: string) {
        const SP_MAP: Record<string, any> = {
            IV: 4,
            IX: 9,
            XL: 40,
            XC: 90,
            CD: 400,
            CM: 900,
        };
        const MAP: Record<string, any> = {
            I: 1,
            V: 5,
            X: 10,
            L: 50,
            C: 100,
            D: 500,
            M: 1000,
        };
        let ss = s;
        Object.keys(SP_MAP).forEach((key: string) => {
            ss = ss.replace(new RegExp(key, "g"), SP_MAP[key] + ",");
        });

        Object.keys(MAP).forEach((key: string) => {
            ss = ss.replace(new RegExp(key, "g"), MAP[key] + ",");
        });
        let sum = 0;
        ss.split(",").forEach((item) => {
            if (item) {
                sum += parseInt(item);
            }
        });
        return sum;
    };
    console.log("romanToInt:" + romanToInt("III"));
})();

/*
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。
    示例 1:
    输入: "()"
    输出: true
    示例 2:
    输入: "()[]{}"
    输出: true
    示例 3:
    输入: "(]"
    输出: false
    示例 4:
    输入: "([)]"
    输出: false
    示例 5:
    输入: "{[]}"
    输出: true
*/

/**
 * @param {string} s
 * @return {boolean}
 */
(function () {
    function isValid(s: string) {
        const vMAP: Record<string, any> = {
            "(": -1,
            "[": -2,
            "{": -3,
            ")": 1,
            "]": 2,
            "}": 3,
        };
        const sArr = Array.from(s);
        const len = sArr.length;
        let checkArr = [];
        let last = "";
        for (let i = 0; i < len; i++) {
            let cur = sArr[i];
            if (checkArr.length > 0 && vMAP[cur] > 0) {
                if (vMAP[cur] + vMAP[last] === 0) {
                    checkArr.pop();
                    last = checkArr[checkArr.length - 1] || "";
                } else {
                    return false;
                }
            } else {
                checkArr.push(sArr[i]);
                last = cur;
            }
        }
        return checkArr.length < 1;
    }
})();
/**
 * 
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000
 

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
 

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
(function () {
    function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
        const mergeArr = nums1.concat(nums2);
        mergeArr.sort((n1: number, n2: number) => {
            return n1 - n2;
        });
        const arr_length = mergeArr.length;

        const mid_pos = Math.floor(arr_length / 2);
        const mid =
            mergeArr.length % 2 === 0
                ? (mergeArr[mid_pos - 1] + mergeArr[mid_pos]) / 2
                : mergeArr[mid_pos];
        return mid;
    }

    console.info(
        "findMedianSortedArrays input: [1,3], [2], output:",
        findMedianSortedArrays([1, 3], [2])
    );
})();

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
(function () {
    class ListNode {
        val: number;
        next: ListNode | null;
        constructor(val?: number, next?: ListNode | null) {
            this.val = val === undefined ? 0 : val;
            this.next = next === undefined ? null : next;
        }
    }

    function bigNumberAdd(num1Arr: string[], num2Arr: string[]) {
        const arr_length = Math.max(num1Arr.length, num2Arr.length);
        let upgradeFlag = false;
        const sumArr: string[] = [];
        for (let i: number = 0; i < arr_length - 1; i++) {
            let n1 = parseInt(num1Arr[i]);
            let n2 = parseInt(num2Arr[i]);
            if (!isNaN(n1) && !isNaN(n2)) {
                let sum = n1 + n2;
                if (upgradeFlag) {
                    upgradeFlag = false;
                    sum += 1;
                }
                if (sum >= 10) {
                    sum = sum % 10;
                    upgradeFlag = true;
                }
                sumArr.push(sum + "");
            } else {
                let sum = !isNaN(n1) ? n1 : n2;
                if (upgradeFlag) {
                    upgradeFlag = false;
                    sum += 1;
                }
                sumArr.push(sum + "");
            }
        }
        return sumArr;
    }

    function addTwoNumbers(
        l1: ListNode | null,
        l2: ListNode | null
    ): ListNode | null {
        let num1Str = "";
        let num2Str = "";
        let target: ListNode | null = l1;
        while (target) {
            num1Str += target.val;
            target = target.next;
        }
        target = l2;
        while (target) {
            num2Str += target.val;
            target = target.next;
        }

        let sumStr = "";
        if (parseInt(num1Str) + parseInt(num2Str) > Number.MAX_SAFE_INTEGER) {
            const num1Arr = num1Str.split("");
            const num2Arr = num2Str.split("");
            const sumArr = bigNumberAdd(num1Arr, num2Arr);
            sumStr = sumArr.reverse().join("");
        } else {
            num1Str = num1Str.split("").reverse().join("");
            num2Str = num2Str.split("").reverse().join("");
            sumStr = parseInt(num1Str) + parseInt(num2Str) + "";
        }
        const ret: ListNode | null = new ListNode();
        let pointer: ListNode | null = null;
        sumStr
            .split("")
            .reverse()
            .forEach((n: string, i: number) => {
                if (i === 0) {
                    ret.val = parseInt(n);
                    return;
                }
                if (!pointer) {
                    pointer = new ListNode(parseInt(n));
                    ret.next = pointer;
                } else {
                    pointer.next = new ListNode(parseInt(n));
                    pointer = pointer.next;
                }
            });
        return ret;
    }

    console.log(JSON.stringify(addTwoNumbers(param1, param2)));
})();

function numWays(n: number): number {
    if (n === 0) return 1;
    else if (n === 1) return 1;

    return numWays(n - 1) + numWays(n - 2);
}
console.log("numWays 7: ", numWays(7));

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 
示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"
 

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

 * 
 */
(function () {
    function longestPalindrome(s: string): string {
        if (!s || s.length === 0) return "";
        let start = 0;
        let end = 0;
        let sizeOdd = 0;
        let sizeEven = 0;
        for (let i = 0; i < s.length; i++) {
            sizeOdd = expendRange(s, i, i);
            sizeEven = expendRange(s, i, i + 1);
            const size = Math.max(sizeEven, sizeOdd);
            console.log(
                "size: %s, sizeOdd: %s, sizeEven: %s",
                size,
                sizeOdd,
                sizeEven
            );
            if (size > end - start) {
                start = i - Math.floor((size - 1) / 2);
                end = i + Math.floor(size / 2);
            }
            console.log("start: %s, end: %s", start, end);
        }
        return s.slice(start, end + 1);
        // return s.substring(start, end + 1);
    }

    function expendRange(s: string, left: number, right: number) {
        let L = left;
        let R = right;
        while (L >= 0 && R < s.length && s[L] === s[R]) {
            L--;
            R++;
        }
        return R - L - 1;
    }
    longestPalindrome("ababd");
});

